package com.yangli.csnote.other;

import java.util.Arrays;

/**
 * http://www.cyc2018.xyz/ 题目原型
 * @Author liyang
 * @Date 2022/10/10 9:56
 */
public class MainOther {
    public static void main(String[] args){
/*        print1ToMaxOfNDigits(2);
        System.out.println(match("abababb", ".*"));

        System.out.println(numDecodings("12"));*/
/*        int[] a = {1, 4, 1, 6};
        System.out.println(Arrays.toString(FindNumsAppearOnce(a)));*/

        System.out.println(LastRemaining_Solution(5, 3));
        System.out.println(LastRemaining_Solution3(5, 3));

        System.out.println(NumberOf1Between1AndN_Solution(1));


    }

    /*
     * 打印从 1 到最大的 n 位数    【递归】
     * 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数即 999。
     * 由于 n 可能会非常大，因此不能直接用 int 表示数字，而是用 char 数组进行存储。
     */
    public static void print1ToMaxOfNDigits(int n){
        if (n < 1) {
            return;
        }
        char[] number = new char[n];//表示要打印的数字，最长为n位
        print1ToMaxOfNDigits(number, 0); //从0位开始给number进行遍历递归并且打印
    }

    private static void print1ToMaxOfNDigits(char[] number, int digit){
        if (digit == number.length) { //当遍历的位超过长度时，表面已经遍历结束打印数据结束一轮递归
            printNumber(number);
            return;
        }
        for (int i = 0; i < 10; i++) {
            number[digit] = (char) (i + '0');//int遍历快速转char  对digit遍历赋值后递归调用对下一位进行遍历赋值
            print1ToMaxOfNDigits(number, digit + 1);
        }
    }

    private static void printNumber(char[] number){
        int index = 0;
        int length = number.length;
        while (index < length && number[index] == '0')//前面为0忽略不打印
            index++;
        while (index < length)
            System.out.print(number[index++]);
        System.out.println();
    }


    /*
     * 正则表达式匹配  【动态规划】
    请实现一个函数用来匹配包括 '.' 和 '*' 的正则表达式。模式中的字符 '.' 表示任意一个字符，而 '*' 表示它前面的字符可以出现任意次（包含 0 次）。
    在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串 "aaa" 与模式 "a.a" 和 "ab*ac*a" 匹配，但是与 "aa.a" 和 "ab*a" 均不匹配。
     */
    public static boolean match(String str, String pattern){
        int m = str.length(), n = pattern.length();
        boolean[][] dp = new boolean[m + 1][n + 1]; //表示 m长度的字符串能否匹配n长度正则表达式，00表示为空串
        dp[0][0] = true; //空串肯定匹配
        for (int j = 1; j <= n; j++) {
            if (pattern.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (pattern.charAt(j - 1) == str.charAt(i - 1) || pattern.charAt(j - 1) == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pattern.charAt(j - 1) == '*') {
                    if (pattern.charAt(j - 2) == str.charAt(i - 1) || pattern.charAt(j - 2) == '.') {
                        dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];
                    } else {
                        dp[i][j] = dp[i][j - 2];
                    }

                }
            }
        }
        return dp[m][n];
    }

    /*
    * 20. 表示数值的字符串    使用正则表达式进行匹配。
    []  ： 字符集合
    ()  ： 分组
    *
    ?   ： 重复 0 ~ 1 次
    +   ： 重复 1 ~ n 次
    *   ： 重复 0 ~ n 次
    .   ： 任意字符
    \\. ： 转义后的 .
    \\d ： 数字
    * */
    public boolean isNumeric(String str){
        if (str == null || str.length() == 0)
            return false;
        return new String(str).matches("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?");
    }

    /*
     * 数字序列中的某一位数字 【快慢指正】
     * 数字以 0123456789101112131415... 的格式序列化到一个字符串中，求这个字符串的第 index 位。
     * */
    public int getDigitAtIndex(int index){
        if (index < 0) {
            return -1;
        }
        if (index < 10) {
            return index;
        }
        int digit = 1; //慢指针 进位
        while (true) {
            int digitCount = getAmountOfDigit(digit);
            if (index < digitCount) {
                return getDigitAtIndex(index, digit);
            }
            index -= digitCount; //快指针 位数
            digit++;
        }

    }

    private int getAmountOfDigit(int digit){//10 90 900 9000 ...
        if (digit == 1) {
            return 10;
        }
        return 9 * (int) (Math.pow(10, digit));
    }

    private int getDigitAtIndex(int index, int digit){
        int start = (int) (Math.pow(10, digit - 1));
        int temp = index % digit;
        int target = start + index / digit;
        return String.valueOf(target).charAt(temp) - '0';
    }


    /*
     * 把数字翻译成字符串 【动态规划】
     * 给定一个数字，按照如下规则翻译成字符串：1 翻译成“a”，2 翻译成“b”... 26 翻译成“z”。一个数字有多种翻译可能，例如 12258 一共有 5 种，分别是 abbeh，lbeh，aveh，abyh，lyh。
     * 实现一个函数，用来计算一个数字有多少种不同的翻译方法。
     * 对于i长度的字符串，可以有两种情况使用一个或者两个字符，dp[i] = d[i]+dp[i-1]
     * */
    public static int numDecodings(String s){
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] dp = new int[s.length() + 1];//dp[i] 表示i长度数组字符串转化为字母的多少种方法
        dp[0] = 1; //定义初始值，空字符串只有一种方法
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }
            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
                dp[i] += dp[i - 2];
            }

        }
        return dp[s.length()];
    }

    /**
     * 扑克牌顺子 五张牌，其中大小鬼为癞子，牌面为 0。判断这五张牌是否能组成顺子。
     * 数组排序=>获取癞子数量=>从非癞子顺序便利=>下一个等于顺序值继续便利，否则消耗癞子继续便利=>如果能便利结束为真，如果癞子为空不能便利为假
     */
    public boolean isContinuous(int[] nums){
        if (nums.length < 5)
            return false;
        Arrays.sort(nums);
        // 统计癞子数量
        int cnt = 0;
        for (int num : nums)
            if (num == 0)
                cnt++;
        // 这个地方写的好 1，从癞子数量为起点 2，数值相等直接返回 3，用数值减法查找差距，根据癞子数量判断就行了
        for (int i = cnt; i < nums.length - 1; i++) {
            if (nums[i + 1] == nums[i])
                return false;
            cnt -= nums[i + 1] - nums[i] - 1;
        }
        return cnt >= 0;
    }

    /*
     * 不用加减乘除做加法
     * a^b 不考虑进位的和 a&b 需要的进位 其实也就是 a^b 和 a&b<<1 的相加
     * */
    public int Add(int a, int b){
        return b == 0 ? a : Add(a ^ b, (a & b) << 1);
    }

    /**
     * 把字符串转换成整数
     */
    public int StrToInt(String str){
        if (str == null || str.length() == 0) {
            return 0;
        }
        boolean nagetive = str.charAt(0) == '-';
        int res = 0;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (i == 0 && (c == '-' || c == '+')) {
                continue;
            }
            if (c < '0' || c > '9') {
                return 0;
            }
            res = res * 10 + (c - '0');
        }
        return nagetive ? -res : res;
    }

    /**
     * 二进制中1的个数
     * n = n&n-1 减少了一个1位
     */
    public int NumberOf1(int n){
        int count = 0;
        while (n != 0) {
            n &= n - 1;
            count++;
        }
/*        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & (1 << i)) == 1) {
                count++;
            }
        }*/

        return count;
    }


    /**
     * 数组中只出现一次的数字 一个整型数组里除了两个数字之外，其他的数字都出现了两次，找出这两个数。
     */
    public static int[] FindNumsAppearOnce(int[] nums){
        int[] res = new int[2];
        int c = 0;
        for (int i = 0; i < nums.length; i++) {
            c ^= nums[i];
        }
        int tag = 0;
        int tag2 = 1 << tag;
        while ((c & tag2) != tag2) {
            tag++;
            tag2 = 1 << tag;
        }
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] & tag2) == tag2) {
                res[0] ^= nums[i];
            } else {
                res[1] ^= nums[i];
            }
        }
        Arrays.sort(res);
        return res;
    }

    /**
     * 数组中出现次数超过一半的数字
     * 多数投票问题，可以利用 Boyer-Moore Majority Vote Algorithm 来解决这个问题，使得时间复杂度为 O(N)。
     */
    public int MoreThanHalfNum_Solution(int[] nums){
        int vote = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (count == 0) {
                count++;
                vote = nums[i];
                continue;
            }
            if (nums[i] == vote) {
                count++;
            } else {
                count--;
            }
        }
        return vote;
    }

    /**
     * 约瑟夫环，圆圈长度为 n 的解可以看成长度为 n-1 的解再加上报数的长度 m。因为是圆圈，所以最后需要对 n 取余。。
     */
    public static int LastRemaining_Solution(int n, int m){
        if (n == 0)     /* 特殊输入的处理 */
            return -1;
        if (n == 1)     /* 递归返回条件 */
            return 0;

        int temp = (LastRemaining_Solution(n - 1, m) + m) % n;
        return temp;
    }

    //当在n-1圈中位置是x时，则n圈中位置是(x+m)%n
    public static int LastRemaining_Solution2(int n, int m){
        int res = 0;//表示 最后出圈哪一位，位置肯定为0
        for (int i = 1; i <= n; i++) { //i表示圈中一共多少人，从最后向上递归  每次遍历表示当为I人数时，最后出圈的那位res再圈中的位置
            res = (res + m) % i; //圈中位置+移动步骤 % 圈中人数
        }
        return res; //当圈为n人时，最后res在圈中位置
    }


    public static int LastRemaining_Solution3(int n, int m){
        if (n == 1)     /* 特殊输入的处理 */
            return 0;

        return (LastRemaining_Solution3(n - 1, m) + m) % n;
    }


    /*
    思路：使用数学方法(先举例)
            你要知道最后的结果是3，带着结果去看问题
        n = 5, m = 3
        第一次，【0, 1, 2, 3, 4】，本轮要踢出2                                  看3
        (下一轮开始从3计数，为了方便读者看出规律，将开始计数的那一位移到开头)
        第二次，【3, 4, 0, 1】，本轮要踢出0                                     看1
        第三次，【1, 3, 4】，本轮要踢出4                                        看1
        第四次，【1, 3】 本轮要踢出1                                            看3
        第五次，【3】
        最后返回3

        我们要使用的数学方法，就是从结果0号位置，反推最开始在哪
        你从第二次，向上看第一次
        你会发现，原来3在0的位置
                现在，3在(0 + 3) % 5
                        => +3 回到上次的位置
                        => %5 防止数组溢出，并且数组本来就是循环数组

        f(n) = ( f(n - 1) + m ) % n
        解释意思：
            f(n) 表示上一次
            f(n - 1) 表示这次，因为我们要从这次回推上一次
            m 表示隔几个
            n表示上一次的数组长度

     */
    public int lastRemaining(int n, int m){
        int res = 0;// 最后只剩下一位，坐标肯定是0
        for (int i = 2; i <= n; i++) {
            res = (res + m) % i;
        }
        return res;
    }


    /**
     * 从 1 到 n 整数中 1 出现的次数
     * 暴力解法
     */
    public static int NumberOf1Between1AndN_Solution1(int n){
        int cnt = 0;
        for (int m = 1; m <= n; m++) {
            int temp = m;
            while (temp != 0) {
                if (temp % 10 == 1) {//每位是不是为1
                    cnt++;
                }
                temp = temp / 10;
            }
        }
        return cnt;
    }


    /*
     * 按照位统计出现的次数
     * 个位出现次数 n/10 + n%10>0?1:0
     * 十位出现次数 n/100  三种情况 n%100 1,大于10 则出现次数为 （n/100）*10*n%10
     * */
    public static int NumberOf1Between1AndN_Solution(int n){
        int cnt = 0;
        for (int m = 1; m <= n; m *= 10) { //从个位开始 个十百千 统计当前位出现的次数
            int a = n / (m * 10), b = n % (m * 10); //统计个位时，跟10取模和求余
            cnt += m * a;//十位以上的 每次都会在个位产生一次1
            if (b >= 2 * m) { //大于2m表示个位肯定出现一次1 大于20表示百位肯定出现10次1
                cnt += m;
            } else if (b >= m) { //大于1m 要根据后位计算
                cnt += b - m + 1;
            }
        }
        return cnt;
    }

}
